#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int size=nums.size();
        int dp[size];
        for(int i=0;i<size;i++){
            dp[i]=1;
        }
//        for(int i=size-1;i>0;i--){
//            for(int j=i-1;j>=0;j--){
//                if(nums[j]<nums[i]){
//                    dp[i]=max(dp[j]+1,dp[i]);
//                }
//            }
//        }
        for(int i=1;i<size;i++){
            for(int j=i-1;j>=0;j--){
                if(nums[j]<nums[i]){
                    dp[i]=max(dp[j]+1,dp[i]);
                }
            }
        }
        int max_=0;
        for(auto x:dp){
            if(max_<x)max_=x;
        }
        return max_;
    }
};
int main(){
    vector<int> nums={1,3,2,4,5,4,1};
    Solution solution;
    cout<<solution.lengthOfLIS(nums);
}